// https://leetcode.cn/problems/trim-a-binary-search-tree
public class TrimBST {
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val)
        {
            this.val = val;
        }
    }
    class Solution {
        public TreeNode trimBST(TreeNode root, int low, int high) {
            if(root == null) return null;
            while(root != null && (root.val < low || root.val > high) )
            {
                if(root.val < low){
                    root = root.right;
                }else
                {
                    root = root.left;
                }
            }
            TreeNode cur = root;
            while(cur != null)
            {
                while(cur.left != null &&  cur.left.val < low)
                {
                    cur.left = cur.left.right;
                }
                cur = cur.left;
            }
            cur = root;
            while(cur != null)
            {
                while(cur.right != null && cur.right.val > high)
                {
                    cur.right = cur.right.left;
                }
                cur = cur.right;
            }
            return root;



        }

    }
}
